package 动态规划;

/**
 * 给定两个字符串 s 和 t，计算 s 的子序列中 t 出现的个数。这里的“子序列”指的是通过删除 s 中的一些字符（可以是任意字符，包括不删除）后，剩下的字符保持原有顺序组成的字符串。
 * 示例
 * 输入：s = "abcde", t = "ace"
 * 输出：1
 * 解释：s 中有一个子序列 "ace"，与 t 完全匹配。
 *  解题思路：使用动态规划来实现，
 *  1：状态转移数组的定义：定义一个二维数组dp，其中dp[i][j] 表示字符串 s 的前 i 个字符，包含了字符串 t 的前 j 个字符的子序列个数。
 *  2：状态转移方程：
 *      如果s[i-1] == t[j-1], 则dp[i][j] = dp[i-1][j-1] + dp[i-1][j]。这里dp[i-1][j-1] 表示匹配当前字符的情况，dp[i-1][j] 表示不匹配当前字符的情况。
 *      如果 s[i-1] != t[j-1]，则 dp[i][j] = dp[i-1][j]，即不匹配当前字符的情况。
 *  3：边界条件的定义：
 *      dp[i][0] = 1，表示空字符串 t 在任何字符串 s 的前缀中都出现一次（即不匹配任何字符）。
 *      dp[0][j] = 0，表示非空字符串 t 在空字符串 s 中无法匹配。
 */
public class L_115 {
    public int numDistinct(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) {
            return 0;
        }
        int m = s.length();
        int n = t.length();

        // dp[i][j] 表示 s 的前 i 个字符中，包含 t 的前 j 个字符的子序列个数
        int[][] dp = new int[m + 1][n + 1];

        // 初始化：空字符串 t 在任何字符串 s 的前缀中都出现一次
        for (int i = 0; i <= m; i++) {
            dp[i][0] = 1;
        }

        // 状态转移
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    // 匹配当前字符和不匹配当前字符的情况
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    // 不匹配当前字符的情况
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[m][n];
    }
}
